from tools_algorithm import *


class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:

        def f(a, b):
            return tasks[a][0] + tasks[b][1] - tasks[a][1] - tasks[b][0]

        ids = list(range(len(tasks)))
        ids.sort(key=cmp_to_key(f))

        c = ans = 0
        for id in ids:
            l, r = tasks[id]
            if c < r:
                ans += r - c
                c = r
            c -= l
        return ans


class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:
        tasks.sort(key=lambda a: a[0] - a[1])
        c = ans = 0
        for l, r in tasks:
            if c < r:
                ans += r - c
                c = r
            c -= l
        return ans


s = Solution()
print(8 == s.minimumEffort([[1, 2], [2, 4], [4, 8]]))
print(32 == s.minimumEffort([[1, 3], [2, 4], [10, 11], [10, 12], [8, 9]]))
print(27 == s.minimumEffort([[1, 7], [2, 8], [3, 9], [4, 10], [5, 11], [6, 12]]))
print(
    s.minimumEffort(
        [
            [5824, 8558],
            [2007, 7182],
            [3756, 5983],
            [3235, 6097],
            [7703, 7861],
            [2676, 3331],
            [456, 610],
            [3926, 7422],
            [762, 1986],
            [3788, 5350],
            [2314, 3069],
            [1574, 3283],
            [4557, 5784],
            [661, 5832],
            [1130, 2735],
            [2104, 4216],
            [3984, 5581],
            [1628, 4013],
            [2601, 5913],
            [1543, 5651],
            [38, 131],
            [1612, 1821],
            [8359, 8698],
            [563, 902],
            [13, 9814],
            [1348, 8549],
            [235, 1184],
            [1178, 1692],
            [85, 1301],
            [1688, 1796],
            [4122, 5067],
            [280, 1976],
            [2986, 3105],
            [4749, 5095],
            [1015, 3627],
            [1925, 7331],
            [4539, 7840],
            [4786, 5709],
            [1876, 3786],
            [112, 1213],
            [112, 143],
            [463, 1219],
            [3166, 9319],
            [883, 4598],
            [747, 1283],
            [8155, 9870],
            [4884, 5496],
            [409, 4033],
            [54, 5316],
            [5883, 6636],
            [1603, 4263],
            [6843, 8654],
            [1450, 6355],
            [2759, 9208],
            [561, 2941],
            [557, 3358],
            [1262, 1754],
            [4292, 4468],
            [10, 9966],
            [3764, 4423],
            [766, 1882],
            [4020, 4189],
            [1, 4],
            [2975, 3112],
            [1372, 3103],
            [111, 1217],
            [3114, 6599],
            [7930, 9269],
            [5907, 9328],
            [1000, 3822],
            [959, 6948],
            [1498, 3591],
            [1255, 4957],
            [5645, 9883],
            [3437, 3572],
            [740, 9023],
            [3509, 6327],
            [1, 27],
            [2969, 7619],
            [4520, 5822],
            [6026, 6962],
            [3922, 4055],
            [3, 1027],
            [227, 4317],
            [1164, 3040],
            [55, 3630],
            [1354, 1436],
            [2697, 8257],
            [3383, 8315],
            [6110, 9781],
            [4212, 4437],
            [2839, 2962],
            [2018, 9695],
            [1225, 2506],
            [1174, 4736],
            [6695, 7854],
            [2469, 3723],
            [1546, 6285],
            [36, 74],
            [5048, 6367],
        ]
    )
    == 249556
)

# c = []
# for _ in range(100):
#     a = random.randint(1, 10**4)
#     b = random.randint(1, a)
#     c.append([b, a])
# f = open("1.txt", "w", encoding="utf-8")
# print(c, file=f)
